/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/find-minimum-in-rotated-sorted-array
   @Language: C++
   @Datetime: 16-02-09 05:49
   */

class Solution {
public:
	/**
	 * @param num: a rotated sorted array
	 * @return: the minimum number in the array
	 * Tip: The origin array can be ascending or descending order
	 */
	int findMin(vector<int> &num) {
		// write your code here
		int begin=0, end=num.size()-1, mid;
		while(begin<end){
			mid = begin+(end-begin)/2;
			if (num[begin]>num[end]){
				if (num[mid]<num[end]) end = mid;
				else begin = mid+1;
			}
			else if (num[mid]<num[begin]) begin = mid+1;
			else end = mid;
		}
		return num[begin];
	}
};
